The present invention relates generally to compressing and decompressing three-dimensional graphics data, and more particularly to compressing and decompressing three-dimensional geometry data corresponding to regularly and irregularly tiled surface portions of graphical objects.
Three-dimensional (3D) computer graphics systems employing large geometric models find wide use in applications such as computer-aided design (CAD), virtual reality environments, training and simulation programs, games, and location-based entertainment. Such systems typically include a 3D graphics accelerator with a specialized rendering subsystem designed to off-load graphics processing functions from the host processor and thereby improving system performance. In a system with a 3D graphics accelerator, an application program executing on the host processor generates data which defines three-dimensional graphics elements for output on a display device. The application program causes the host processor to transfer this data to the graphics accelerator. The graphics accelerator then receives the data and renders the corresponding graphics elements on the display device.
To improve rendering speed and increase the realism of rendered images, techniques such as level of detail (LOD) switching may be used. LOD switching typically involves using more detailed images or textures for objects in the foreground of a scene and using less detailed images of textures for objects in the background.
For example, when a wall that is in foreground, surface texture details such as a pattern of brick may be used. In contrast, for a wall that is in the distant background, less detail may be used. The details of the background wall may be removed to mimic the actual blurred appearance of distance walls in the real world. One way to implement LOD switching is to use polygon simplification. Polygon simplification involves reducing the number of polygons used to represent an object.
To further improve rendering speeds, many graphics accelerators implement a technique called visibility culling. Visibility culling involves removing invisible objects or portions of objects from the scene being rendered. This technique, however, is not efficient when most objects are visible. In such cases, the full amount of geometry data are transferred from the host processor to the rendering hardware on the graphics accelerator.
This transmission of graphics primitives and commands from the host processor to the graphics accelerator over the system bus is one of the major bottlenecks in computer graphics. This bottleneck is becoming more problematic as users of graphics applications programs require an ever-increasing amount of complexity (and hence, size) in the geometric models used to produce visualization effects. The result is that slow memory subsystems or slow bus subsystems may not be able to adequately supply geometry data to the relatively fast real-time rendering hardware. This compromises system performance. In addition, the size requirements for a large set of geometric data may also cause memory constraints.
For example, rendering a large geometric data set with one million triangles at 30 Hz may require a system bus throughput of approximately 720 MB/sec (at a ratio of 24 bytes/triangle). While such high bus bandwidths may be attainable for high-end systems, low-end to mid-range systems typically have bandwidths on the order of 250-320 MB/sec. The performance of lower cost systems is thus affected by the throughput of the system bus as geometry processing requirements increase.
Many prior art systems utilize algorithms that reduce the number of vertices present in the geometric data One such algorithm is vertex decimation. Vertex decimation attempts to reduce the total number of polygons in a surface portion without loss of important detail. A paper by Schroeder, William J. and Jonathan A. Zarge, and William E. Lorensen entitled, xe2x80x9cDecimation of Triangle Meshes,xe2x80x9d Proceedings of SIGGRAPH ""92 (Chicago, Ill., Jul. 26-31, 1992), in ACM Computer Graphics, vol. 26, no. 2, pp. 65-70, July 1992, describes one form of vertex decimation in greater detail, and is hereby incorporated by reference in its entirety. However, the compression achievable by reducing the number of vertices is limited. In particular, once the number of vertices drops below a certain level, image quality may drop quickly. Thus, graphics professionals have sought ways to compress the graphics data remaining after the number of vertices have been reduced to desired levels.
Applicant""s above-referenced parent patent applications disclose two such methods for compressing three-dimensional graphics data. The first application (Ser. No. 08/511,294) discloses a method and system for compression of 3D geometry, preferably compression of strips of three-dimensional triangles. The second application (Ser. No. 08/988,202) discloses a method and system optimized for geometry compression of regular surface portions in the 3D geometry data With either system, if the compression is performed as a pre-process, the geometry may be stored in main memory of the computer system in a compressed format. The geometry data is then transferred to the computer system""s graphics hardware in compressed format to reduce memory and bus bandwidth requirement. Decompression may then be performed by the graphics hardware either off-line (e.g., using software decompression) or in real-time (e.g., using hardware or software decompression).
Applicant""s above-referenced parent patent applications disclose two different methods for compressing geometry data, one optimized for regular surfaces and one optimized for irregular surfaces. However, no provisions are made for dealing with three-dimensional graphics data that comprises both regularly tiled and irregular tiled surfaces. For example, FIG. 1 illustrates a 3D object (a refrigerator) having mostly regularly tiled surfaces, while FIG. 2 illustrates a 3D object (a lion) having mostly irregularly tiled surfaces. FIG. 3, however, illustrates a 3D object (a bear) having a mixture of regularly tiled and irregularly tiled surfaces.
Due to the mixture of both regularly tiled and irregularly tiled surfaces in FIG. 3, neither method disclosed in the parent applications is optimized for this data. Thus, a new method for efficiently compressing 3D geometric data comprising both regular and irregular surfaces is needed.
The problems outlined above may in part be solved by a method for compressing 3D geometry data that is capable of efficiently compressing both regularly tiled and irregularly tiled surfaces. In one embodiment, the method comprises examining 3D geometry data to detect the presence of regularly tiled surface portions. The regularly tiled surface portions may then be compressed using a first encoding method, while the remaining irregularly tiled surface portions may be compressed using a second encoding method, wherein the second encoding method is different from the first encoding method. Advantageously, the first encoding method may be optimized for regularly tiled surface portions, while the second encoding method may be optimized for irregularly-tiled surface portions. Note as used herein the term xe2x80x9cirregularly tiledxe2x80x9d refers to any tiled surface portion that does not meet predetermined qualifications for being classified as a regularly tiled surface portion.
In one embodiment, the first encoding method may encode the regularly tiled surface portions as vertex rasters. Thus, the vertices are arranged in a scan pattern (e.g., in rows and columns that form a rectangular array of vertices) which is scanned in a predetermined pattern (e.g., from side to side in lines from top to bottom). As part of the vertex raster, an xe2x80x9cextent valuexe2x80x9d may be encoded for each regularly tiled surface portion. The extent values may be used to define the particular arrangement of the vertices within the regularly tiled surface portion. For example, the extent value may indicate that the vertices in the raster from a 8xc3x974 rectangular array.
In one embodiment, the first encoding method may comprise: (1) specifying an extent value for the vertex raster, (2) specifying initial values for selected interpolatable parameters for one or more of the vertices, and (3) specifying delta values indicative of how the selected parameters vary across the vertex raster. Per-vertex information may be specified for certain vertices within the raster that have vertex parameters which deviate from the specified delta values. Per-vertex information for vertices that do not deviate from the specified delta values, but have additional information not represented by the delta values, may also be explicitly specified. In one embodiment, the per-vertex information may also be compressed (e.g., by reducing the number of bits used to represent the constituent vertex parameter values) to reduce the overall size of the graphics data even further. Note, as used herein, vertex parameter values may include, but need not be limited to, position information, normal information, color information, lighting information, specular reflectivity information, material information, and texture information.
The second encoding method may encode the irregularly tiled surface portions by using geometry compression. A number of different geometry compression techniques may be utilized (e.g., normal compression, and mesh buffers).
In one embodiment, the compression method may embed opcodes within the compressed graphics data to indicate how the each vertex is encoded (i.e., either as part of a regularly tiled surface or as part of an irregularly tiled surface). Alternatively, opcodes may be embedded that are indicative of whether the surface following the opcode in the compressed geometry data is encoded using the first method or the second method. In either case, the opcodes may be either fixed- or variable-length. For example, in one embodiment the variable-length opcode may comprise a header and a body, wherein the header indicates the length of the opcode, and wherein the body contains information regarding the following vertices and/or surfaces. In other embodiments, different indicators may be used instead of opcodes. For example, tags or indicator bits may be used to demarcate changes in compression method within the stream of compressed geometry data.
Optionally, error checking and correction (ECC) and encryption information may also be generated for (or as part of) the compressed 3D geometry information. Once compressed, the 3D geometry information may be stored on computer readable media and distributed for future decoding. Alternatively, the compressed data may be transmitted across a computer network.
In one embodiment, the compression may detect regularly tiled surfaces by scanning the geometry data for groups of vertices (e.g., rectangular arrays of 32 vertices or greater) that each have one or more parameters that change in a predictable manner (e.g., parameters that may be delta encoded using a predetermined maximum number of bits). These pluralities of selected vertices may be encoded using the encoding method optimized for regular surfaces (e.g., using delta encoding or delta-delta encoding). Note the groups of vertices (i.e., the vertex rasters) need not be limited to two-dimensional array of evenly spaced vertices. For example, the vertices may be spaced according to a small number of different polygons. For example, the polygons may be rectangles, rhombuses, triangles, hexagons, or parallelograms.
In another embodiment, the method for compressing 3D geometry data may comprise encoding different surface portions at different compression rates depending upon each surface portion""s individual attributes. For example a surface portion that has little variation in vertex parameters may be compressed using delta encoding with only a few bits allocated for the delta values to achieve high compression rations. Surface portions that have larger variations in vertex parameters may be delta encoded with a larger number of bits allocated for delta values.
In another embodiment, the method may comprise converting the geometry data into a mesh format. The mesh format may include at least one irregular polygonal mesh portion, and at least one regular polygonal mesh portion. The regular polygonal mesh portion may be characterized by having a regular arrangement of vertices defining polygons. The irregular polygonal mesh portions may be compressed using a first compression method. The regular polygonal mesh portions may be compressed using a second compression method. The second compression method, however, may be configured to utilize the regular arrangement of the vertices to achieve a second level of compression different than the level of compression achieved by the first compression method. The regular polygonal mesh portions may be characterized by having a regular arrangement of homogeneous polygonal mesh portions.
In one embodiment, a software program for compression of three-dimensional graphics data is also contemplated. The software may comprise a plurality of instructions configured to detect regular surface portions within three-dimensional graphics data. The regular surface portions may have vertices with one or more properties that change in a predictable manner. The instructions may be further configured to compress irregular surface portions using a first compression method, and to compress irregular surface portions using a second compression method which achieves a different compression rate than the first compression method. The software program may be further configured to embed opcodes within the compressed data, wherein the opcodes are indicative of which type of compression was used on the corresponding surface portion or portions.